// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func minDistance(word1 string, word2 string) int {
	if len(word1) == 0 || len(word2) == 0 {
		fmt.Print(len(word1) + len(word2))
	}

	word1 = " " + word1
	word2 = " " + word2

	// 创建二维数组 array
	array := make([][]int, len(word1))
	for i := 0; i < len(word1); i++ {
		array[i] = make([]int, len(word2))
	}

	for i := 0; i < len(word1); i++ {
		array[i][0] = i
	}

	for i := 0; i < len(word2); i++ {
		array[0][i] = i
	}

	for i := 1; i < len(word1); i++ {
		for j := 1; j < len(word2); j++ {
			if word1[i] != word2[j] {
				array[i][j] = min(array[i][j-1], array[i-1][j]) + 1
			} else {
				array[i][j] = array[i-1][j-1]
			}
		}
	}

	return array[len(word1)-1][len(word2)-1]
}

func min(x int, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	str1 := "abcde"
	str2 := "ace"
	res := minDistance(str1, str2)
	fmt.Println(res)
}

//$ go run interview11-3.go
//2
